package 题目集.动态规划.区间dp;

import org.junit.Test;

import java.util.Arrays;

/**
 * 给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。
 * 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。
 * https://leetcode.cn/problems/longest-palindromic-subsequence/
 */

public class 最长回文子序列 {
    /**
     * 思路1：可以把字符串反转，然后求最长公共子序列
     * 思路2：范围dp
     */
    public int longestPalindromeSubseq(String str) {
        s = str.toCharArray();
        dp = new int[s.length][s.length];
        for (int[] ints : dp) {
            Arrays.fill(ints, -1);
        }
//        return dfs(0, s.length - 1);
        return dpFun(s.length);
    }

    char[] s;
    int[][] dp;
    public int dfs(int l, int r) {
        if (dp[l][r] != -1) return dp[l][r];
        if (l == r) return 1;
        if (l + 1 == r) return s[l] == s[r] ? 2 : 1;
        if (s[l] == s[r]) {
            dp[l][r]=dfs(l + 1, r - 1) + 2;
        }else {
            dp[l][r]=Math.max(dfs(l + 1, r), dfs(l, r - 1));
        }
        return dp[l][r];
    }

    public int dpFun(int n) {
        int[][] dp = new int[n][n];
        for (int i = 0; i < n; i++) {
            dp[i][i] = 1;
        }
        for (int i = 0; i < n-1; i++) {
            dp[i][i + 1] = (s[i] == s[i + 1]) ? 2 : 1;
        }
        //这里减2和加2是减去上面两个base case
        for (int i = n - 3; i >= 0; i--) {  //这里-3是因为n是开区间
            for (int j = i + 2; j < n; j++) {
                if (s[i] == s[j]) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][n-1];
    }
    @Test
    public void test() {
        System.out.println(longestPalindromeSubseq("bbbab"));
    }
}
